/*
https://leetcode.cn/problems/kth-missing-positive-number/submissions/565524588/
二分搜索
2024/9/14
*/

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int nummiss = 0; // 记录缺失的正整数的数量
        int nlast = -1;  // 用于记录上一个缺失的正整数
        int ncurr = 1;   // 当前检查的正整数
        int ptr = 0;     // 指向数组中下一个要比较的元素的指针

        // 遍历直到找到第k个缺失的正整数
        for (nummiss = 0; nummiss < k; ++ncurr) {
            // 如果当前正整数与数组中的元素相等，则移动指针到下一个元素
            if (ncurr == arr[ptr]) {
                // 如果指针没有超出数组范围，则向前移动
                ptr = (ptr + 1 < arr.size()) ? ptr + 1 : ptr;
            } else {
                // 当前正整数不在数组中，因此是一个缺失的正整数
                ++nummiss;
                nlast = ncurr; // 更新最后缺失的正整数为当前值
            }
        }
        // 返回第k个缺失的正整数
        return nlast;
    }
};